#!/usr/bin/python
# Filename: KTree.py

# K-branch Tree

# k-tree has many similar conception and property to b-tree:
# full k-tree, complete k-tree, and so on.

# extend k-tree: add leaf as child to every possible node
# 1) after externsion, the tree becomes full, and added leaf = (k-1)(original node) + 1
# prove(induction):
# assumption: None reference of node is called degree.
# when add child to tree, it's degree +(k-1)
# tree of root(1 node) has degree of k = (k-1)+1, so tree of n nodes has (k-1)n+1 degree.
# when extending, add count of degree leafs to the tree, that is (k-1)n+1 = (k-1)(node)+1
# 2) extended path length E, internal path length I, E = (k-1)I + kn
# prove(induction):
# when tree of root(1 node), E = k, I = 0, it's obviously true.
# assume that when tree of n nodes, E(n) = (k-1)I(n) + kn is true.
# when add a leaf(n+1), after extension, delete the original leaf which length of path is l.
# I(n) = I(n+1) - l, E(n) = E(n+1) -k(l+1) + l = E(n+1) - (k-1)l - k,
# -> E(n+1) = E(n)+(k-1)l+k = (k-1)I(n)+kn+(k-1)l+k = (k-1)I(n+1)-(k-1)l+kn+(k-1)l+k = (k-1)I(n+1) + k(n+1).

# property of k-tre
# 0) n = e + 1
# this is the property of non-ring connected graph
# 1) full k-tree theorem: leaf = (k-1)branch + 1, proved before.
# n = l + b, n-1 = kb(full k-tree, kb edges, every n except root(n-1) has an edge linked with its parent)
# -> l+b = kb + 1 -> l = (k-1)b + 1
# 2) inferene from full k-tree theorem:
# a non-empty k-tree's None reference = (k-1)node + 1
# -3) any k-tree, 0-degree nodes = k-degree nodes + 1
# n = n0 + n1 + n2 + n3 + ..., n = e + 1
# e = n1 + 2*n2 + 3*n3 + ...-> n = n1 + 2*n2 + 3*n3 + ... + 1
# -> n0 = n2 + 2*n3 + ... + (k-1)nk + 1 
# 4) in level j, there are at most k^j nodes
# 5) in h-height k-tree, there are at most k^l-1 nodes
# 6) height of n-node complete k-tree is upper[log(k)(n+1)]

# storage
# when k increasing, size of branch will increase bcz of reference,
# so there should be difference between leaf and branch in storage to keep space efficiency.
